
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_INPUT_LEN 100  // 输入数组最大长度
#define MAX_RESULT_CNT 1024// 最大子集数（2^10=1024，2^20=1048576，按需调整）

// 动态数组（模拟Python list，存储void*类型，支持任意数据）
typedef struct {
    void** data;
    int size;
    int capacity;
} DynamicArray;

// 初始化动态数组
DynamicArray* da_init(int init_capacity) {
    DynamicArray* da = (DynamicArray*)malloc(sizeof(DynamicArray));
    if (!da) return NULL;
    da->capacity = init_capacity > 0 ? init_capacity : 4;
    da->data = (void**)malloc(da->capacity * sizeof(void*));
    da->size = 0;
    return da;
}

// 动态数组扩容
static bool da_resize(DynamicArray* da) {
    if (!da) return false;
    int new_cap = da->capacity * 2;
    void** new_data = (void**)realloc(da->data, new_cap * sizeof(void*));
    if (!new_data) return false;
    da->data = new_data;
    da->capacity = new_cap;
    return true;
}

// 向动态数组添加元素
bool da_add(DynamicArray* da, void* elem) {
    if (!da) return false;
    if (da->size >= da->capacity && !da_resize(da)) {
        fprintf(stderr, "动态数组扩容失败\n");
        return false;
    }
    da->data[da->size++] = elem;
    return true;
}

// 释放动态数组（elem_free：元素释放函数，NULL表示不释放元素）
void da_destroy(DynamicArray* da, void (*elem_free)(void*)) {
    if (!da) return;
    if (elem_free) {
        for (int i = 0; i < da->size; i++) {
            elem_free(da->data[i]);
        }
    }
    free(da->data);
    free(da);
}

// 复制整数动态数组（用于整数子集）
DynamicArray* da_copy_int(const DynamicArray* src) {
    if (!src) return NULL;
    DynamicArray* dest = da_init(src->size);
    if (!dest) return NULL;
    for (int i = 0; i < src->size; i++) {
        int* val = (int*)malloc(sizeof(int));
        *val = *(int*)src->data[i];
        da_add(dest, val);
    }
    return dest;
}

// 复制字符串动态数组（用于字符串子集）
DynamicArray* da_copy_str(const DynamicArray* src) {
    if (!src) return NULL;
    DynamicArray* dest = da_init(src->size);
    if (!dest) return NULL;
    for (int i = 0; i < src->size; i++) {
        char* str = (char*)malloc(strlen((char*)src->data[i]) + 1);
        strcpy(str, (char*)src->data[i]);
        da_add(dest, str);
    }
    return dest;
}

// 打印整数子集结果
void print_int_subsets(DynamicArray* result) {
    printf("[");
    for (int i = 0; i < result->size; i++) {
        DynamicArray* subset = (DynamicArray*)result->data[i];
        printf("[");
        for (int j = 0; j < subset->size; j++) {
            printf("%d", *(int*)subset->data[j]);
            if (j != subset->size - 1) {
                printf(", ");
            }
        }
        printf("]");
        if (i != result->size - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

// 打印字符串子集结果
void print_str_subsets(DynamicArray* result) {
    printf("[");
    for (int i = 0; i < result->size; i++) {
        DynamicArray* subset = (DynamicArray*)result->data[i];
        printf("[");
        for (int j = 0; j < subset->size; j++) {
            printf("\"%s\"", (char*)subset->data[j]);
            if (j != subset->size - 1) {
                printf(", ");
            }
        }
        printf("]");
        if (i != result->size - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

// 释放整数子集结果集（递归释放）
void free_int_subsets(DynamicArray* result) {
    if (!result) return;
    for (int i = 0; i < result->size; i++) {
        DynamicArray* subset = (DynamicArray*)result->data[i];
        da_destroy(subset, free);
    }
    da_destroy(result, NULL);
}

// 释放字符串子集结果集（递归释放）
void free_str_subsets(DynamicArray* result) {
    if (!result) return;
    for (int i = 0; i < result->size; i++) {
        DynamicArray* subset = (DynamicArray*)result->data[i];
        da_destroy(subset, free);
    }
    da_destroy(result, NULL);
}

// ========================= 二项组合树解法（整数数组） =========================
DynamicArray* combinations_int(const int* input, int len) {
    if (len <= 0 || len > MAX_INPUT_LEN) {
        fprintf(stderr, "输入数组长度无效\n");
        return NULL;
    }

    DynamicArray* result = da_init(MAX_RESULT_CNT);
    if (!result) return NULL;

    // 队列元素：DynamicArray*（当前子集） + int（起始索引）
    typedef struct {
        DynamicArray* subset;
        int start_idx;
    } QueueItem;

    // 初始化队列（用动态数组模拟队列，FIFO）
    DynamicArray* queue = da_init(len * 2);
    if (!queue) {
        da_destroy(result, NULL);
        return NULL;
    }

    // 初始元素：空子集 + 起始索引0
    DynamicArray* empty_subset = da_init(0);
    QueueItem* init_item = (QueueItem*)malloc(sizeof(QueueItem));
    init_item->subset = empty_subset;
    init_item->start_idx = 0;
    da_add(queue, init_item);

    while (queue->size > 0) {
        // 出队（FIFO：取第一个元素）
        QueueItem* item = (QueueItem*)queue->data[0];
        // 移除队首元素（移动后续元素）
        for (int i = 0; i < queue->size - 1; i++) {
            queue->data[i] = queue->data[i + 1];
        }
        queue->size--;

        // 将当前子集加入结果集（复制一份，避免后续修改影响）
        DynamicArray* subset_copy = da_copy_int(item->subset);
        da_add(result, subset_copy);

        // 生成子节点：从start_idx开始遍历剩余元素
        int start = item->start_idx;
        for (int i = 0; i < len - start; i++) {
            int curr_idx = start + i;
            // 复制当前子集，添加新元素
            DynamicArray* new_subset = da_copy_int(item->subset);
            int* val = (int*)malloc(sizeof(int));
            *val = input[curr_idx];
            da_add(new_subset, val);

            // 入队：新子集 + 下一个起始索引（curr_idx + 1）
            QueueItem* new_item = (QueueItem*)malloc(sizeof(QueueItem));
            new_item->subset = new_subset;
            new_item->start_idx = curr_idx + 1;
            da_add(queue, new_item);
        }

        // 释放当前队项的内存
        da_destroy(item->subset, free);
        free(item);
    }

    // 释放队列
    da_destroy(queue, NULL);
    return result;
}

// ========================= 二项组合树解法（字符串数组） =========================
DynamicArray* combinations_str(const char* input[], int len) {
    if (len <= 0 || len > MAX_INPUT_LEN) {
        fprintf(stderr, "输入数组长度无效\n");
        return NULL;
    }

    DynamicArray* result = da_init(MAX_RESULT_CNT);
    if (!result) return NULL;

    typedef struct {
        DynamicArray* subset;
        int start_idx;
    } QueueItem;

    DynamicArray* queue = da_init(len * 2);
    if (!queue) {
        da_destroy(result, NULL);
        return NULL;
    }

    // 初始元素：空子集 + 起始索引0
    DynamicArray* empty_subset = da_init(0);
    QueueItem* init_item = (QueueItem*)malloc(sizeof(QueueItem));
    init_item->subset = empty_subset;
    init_item->start_idx = 0;
    da_add(queue, init_item);

    while (queue->size > 0) {
        // 出队（FIFO）
        QueueItem* item = (QueueItem*)queue->data[0];
        for (int i = 0; i < queue->size - 1; i++) {
            queue->data[i] = queue->data[i + 1];
        }
        queue->size--;

        // 加入结果集
        DynamicArray* subset_copy = da_copy_str(item->subset);
        da_add(result, subset_copy);

        // 生成子节点
        int start = item->start_idx;
        for (int i = 0; i < len - start; i++) {
            int curr_idx = start + i;
            DynamicArray* new_subset = da_copy_str(item->subset);
            char* str = (char*)malloc(strlen(input[curr_idx]) + 1);
            strcpy(str, input[curr_idx]);
            da_add(new_subset, str);

            QueueItem* new_item = (QueueItem*)malloc(sizeof(QueueItem));
            new_item->subset = new_subset;
            new_item->start_idx = curr_idx + 1;
            da_add(queue, new_item);
        }

        // 释放内存
        da_destroy(item->subset, free);
        free(item);
    }

    da_destroy(queue, NULL);
    return result;
}

// ========================= 位运算解法（整数数组） =========================
DynamicArray* subsets_int(const int* input, int len) {
    if (len <= 0 || len > 20) {  // 2^20=1048576，超过则子集数过多
        fprintf(stderr, "输入数组长度不能超过20\n");
        return NULL;
    }

    int total = 1 << len;  // 子集总数：2^len
    DynamicArray* result = da_init(total);
    if (!result) return NULL;

    // 遍历所有掩码（0 ~ 2^len - 1）
    for (int mask = 0; mask < total; mask++) {
        DynamicArray* subset = da_init(len);
        for (int i = 0; i < len; i++) {
            // 检查第i位是否为1（存在该元素）
            if (mask & (1 << i)) {
                int* val = (int*)malloc(sizeof(int));
                *val = input[i];
                da_add(subset, val);
            }
        }
        da_add(result, subset);
    }

    return result;
}

// ========================= 位运算解法（字符串数组） =========================
DynamicArray* subsets_str(const char* input[], int len) {
    if (len <= 0 || len > 20) {
        fprintf(stderr, "输入数组长度不能超过20\n");
        return NULL;
    }

    int total = 1 << len;
    DynamicArray* result = da_init(total);
    if (!result) return NULL;

    for (int mask = 0; mask < total; mask++) {
        DynamicArray* subset = da_init(len);
        for (int i = 0; i < len; i++) {
            if (mask & (1 << i)) {
                char* str = (char*)malloc(strlen(input[i]) + 1);
                strcpy(str, input[i]);
                da_add(subset, str);
            }
        }
        da_add(result, subset);
    }

    return result;
}

int main() {
    // ========================= 测试二项组合树解法 =========================
    printf("=== 二项组合树解法（字符串数组 ['A','B','C']）===\n");
    const char* str_input[] = {"A", "B", "C"};
    int str_len = sizeof(str_input) / sizeof(str_input[0]);
    DynamicArray* comb_str = combinations_str(str_input, str_len);
    print_str_subsets(comb_str);
    free_str_subsets(comb_str);

    // ========================= 测试位运算解法 =========================
    printf("\n=== 位运算解法（整数数组 [1,2,3]）===\n");
    int int_input[] = {1, 2, 3};
    int int_len = sizeof(int_input) / sizeof(int_input[0]);
    DynamicArray* subsets_int_res = subsets_int(int_input, int_len);
    print_int_subsets(subsets_int_res);
    free_int_subsets(subsets_int_res);

    return 0;
}